package com.wtgroup.demo.leetcode.q034_在排序数组中查找元素的第一个和最后一个位置;

import java.util.Arrays;

public class Q034_My {
    public static void main(String[] args) {
        int[] nums = {1};
        Q034_My exe = new Q034_My();
        int[] res = exe.searchRange_2(nums, 1);
        System.out.println(Arrays.toString(res));
    }

    /**
     * M1:
     * 二分, 定位到了后, 向左右扩散.
     *
     * 复杂度: 最坏情况O(n)
     */
    public int[] searchRange(int[] nums, int target) {

        int n = nums.length;
        int left = 0, right = n-1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                int p,t; p=t=mid;
                while (p>0 && nums[p-1]==target) {--p;}
                while (t<n-1 && nums[t+1] == target) {++t;}
                return new int[]{p, t};
            }
            if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return new int[]{-1, -1};
    }

    /**
     * M2: 分别二分找第一个大于等于的和第一个大于的.
     *
     * 复杂度: O(logn)
     * */
    public int[] searchRange_2(int[] nums, int target) {
        int[] ans = new int[]{-1,-1};
        int left = binSearch(nums, target, true);
        if (left == nums.length || nums[left] != target) {
            return ans;
        }
        int right = binSearch(nums, target, false) -1;
        if (nums[right] != target) {
            return ans;
        }

        return new int[]{left, right};
    }

    private int binSearch(int[] nums, int target, boolean lower) {
        int n = nums.length;
        int left=0, right = n-1;
        // 第一个大于等于的: >= 取左, 看还有没有满足的但更前面的. 记录当前值.
        // 第一个大于的: > 取左, 看还有没有满足的但更前面的. 记录当前值.
        int ans = n;
        while (left <= right) {
            int mid = (left+right) / 2;
            if ((lower && nums[mid] >= target) || nums[mid] > target) {
                right = mid-1;
                ans = mid; // 记录这轮的位置, 以防下一轮再也找不到了, [骑驴找马].
            } else {
                left = mid+1;
            }
        }

        return ans;
    }
}
